Para realizar el análisis de complejidad, analizaremos el pseudocódigo de nuestra implementación del algoritmo: \\

\subsubsection{pseudocodigo}
	\begin{pseudo}
		\func{UbicarCentrales}{$arreglo(pueblo) pueblos,int cantPueblo, int cantCentrales$}\\
		1 \tab\tab\tab define pueblo $= <int , int >$ \\
		2 \tab\tab\tab define arista $= <int , int >$ \\
		3 \tab\tab\tab matriz nodoXdist $=$ nueva matriz[cantPueblo][cantPueblo] \tOde{n^2}\\
		4 \tab\tab\tab \FOR (int j $=$ 0 ; j$<$cantPueblo ; j++)\\
		5 \tab\tab\tab\tab \FOR (int i $=$ 0 ; i$<$cantPueblo ; i++)\\
		6 \tab\tab\tab\tab\tab  nodoXdist[i][j] $=$ distancia(pueblos[i],pueblos[j]) \tOde{1}\\
		7 \tab\tab\tab arreglo(arista) aristas $=$ nuevoArreglo(cantPueblos-1) \tOde{n}\\
		8 \tab\tab\tab prim(nodoXdist,aristas) \tOde{n^2}\\
		9 \tab\tab\tab mergesort(aristas) \tOde{n*log(n)}\\
		10\tab\tab\tab matriz adyacencias $=$ nueva matriz[cantPueblo][cantPueblo] \tOde{n^2}\\
		11\tab\tab\tab arreglo(bool) conectadoAcentral $=$ nuevo arreglo(cantPueblo) \tOde{n}\\
		12\tab\tab\tab arreglo(bool) recorridos $=$ nuevo arreglo(cantPueblo) \tOde{n^2}\\
		13\tab\tab\tab stack(pueblo) nodosRecorridos \tOde{1}\\
		14\tab\tab\tab pilaPueblos.push(0) \tOde{1}\\
		15\tab\tab\tab \FOR(int i $=$ 0 ; i$<$cantPueblo ; i++)\\
		16\tab\tab\tab\tab adyacencias[aristas[i].idNodo1][aristas[i].idNodo2] $=$ 1 \tOde{1}\\
		17\tab\tab\tab\tab adyacencias[aristas[i].idNodo2][aristas[i].idNodo1] $=$ 1 \tOde{1}\\
		18\tab\tab\tab \WHILE (!nodosRecorridos.vacia())\\
		20\tab\tab\tab\tab  actual $=$ nodosRecorridos.top() \tOde{1}\\
		21\tab\tab\tab\tab  nodosRecorridos.pop() \tOde{1}\\
		22\tab\tab\tab\tab \FOR (int i $=$ 0 ; i$<$cantPueblo ; i++)\\
		23\tab\tab\tab\tab\tab \IF (adyacencias[actual][i] $==$ 1 \&\& !recorridos[i]) \tOde{1}\\
		24\tab\tab\tab\tab\tab\tab nodosRecorridos.push(i), recorridos[i] $=$ true \tOde{1}\\
		25\tab\tab\tab\tab \IF (nodosRecorridos.vacia()) \tOde{1}\\
		26\tab\tab\tab\tab\tab centrales[centralActual] = pueblos[actual]\tOde{1}\\
		27\tab\tab\tab\tab\tab centralActual+1, proximo $=$ 0 \tOde{1}\\
		28\tab\tab\tab\tab\tab encontreProximo $=$ false \tOde{1}\\
		29\tab\tab\tab\tab\tab \WHILE (!encontreProximo \&\& proximo $<$ cantPueblos)\\
		30\tab\tab\tab\tab\tab\tab \IF (!recorridos[proximo]) \tOde{1}\\
		31\tab\tab\tab\tab\tab\tab\tab actual $=$ proximo \tOde{1}\\
		32\tab\tab\tab\tab\tab\tab\tab nodosRecorridos.push(proximo) \tOde{1}\\
		33\tab\tab\tab\tab\tab\tab\tab encontreProximo $=$ true \tOde{1}\\
		34\tab\tab\tab\tab\tab\tab\tab recorridos[proximo] $=$ true \tOde{1}\\
		35\tab\tab\tab\tab\tab\tab \ELSE proximo++; \tOde{1}\\
		36\tab\tab\tab arreglo(arista) tuberias $=$ new arista[cantPueblos-cantCentrales+1]; \tOde{n}\\
		37\tab\tab\tab int j $=$ 0 \tOde{1}\\
		38\tab\tab\tab \FOR (int i $=$ cantCentrales-1 ; i $<$ cantPueblos ; i++) \\
		39\tab\tab\tab\tab tuberias[j] $=$ aristas[i] \tOde{1}\\
		40\tab\tab\tab\tab j++ \tOde{1}\\
		41\tab\tab\tab tuberiasConstruidas $=$ j-1 \tOde{1}\\		
		42\tab\tab\tab return pair$<$arreglo(pueblo),arreglo(arista)$>$ make_pair(centrales,tuberias)\\
	\end{pseudo}
	
El algoritmo de PRIM y el MERGESORT fueron sacados del libro Fundamentos de Algoritmia de los autores G. Brassard y P. Bratley.\\
En el caso del Algoritmo de PRIM la complejidad es \Ode{n^2}, el Mergesort por su lado tiene complejidad \Ode{n*log(n)} siendo n la cantidad de pueblos, 
esto es porque el AGM que nos devuelve el algoritmo de PRIM tiene n-1 aristas.\\
El \FOR de las líneas 5,6 se ejecuta n veces, y el \FOR externo (linea 4) se ejecuta n veces, por lo tanto la complejidad en esas líneas es de \tOde{n^2}.\\
El \FOR de las líneas 15,16 y 17 se ejecuta n veces y como las líneas internas son \Ode{1}, el total es \Ode{n}.\\
El \WHILE de las líneas 18-35 se ejecuta n veces, se van pusheando en un stack los números de los nodos a visitar y se van sacando cuando ya se utilizaron.
Luego el \FOR en las líneas 22-24 se ejecuta n veces en el peor caso y se van pusheando los vecinos al elemento actual y el \WHILE en las líneas 29-35 se 
ejecuta n veces en el peor caso, siendo el mismo el que no recorra todo el arreglo de recorridos buscando cual es el próximo a recorrer y siendo el último elemento, 
por lo tanto el costo total del ciclo de las líneas 18-35 es \Ode{n^2}.\\
El \FOR de las líneas 38-40 se ejecuta n-1 veces en el peor caso, ya que sería el caso que tenga una sola central y comienza a recorrer desde el primero.
La complejidad total del algoritmo es \Ode{n*log(n)}+\Ode{n^2} = \Ode{n^2}.
